import java.util.ArrayList;

/**
 * Created by forcht on 2018/4/28.
 */
public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> list=new ArrayList<>();
        if(n<0)return list;
        if (n==0){
            list.add(0);
            return list;
        }
        list.add(0);
        list.add(1);
        for(int i=2;i<=n;i++){
            int size=list.size()-1;
            for(int j=size;j>=0;j--){
                list.add(list.get(j)+(1<<(i-1)));
            }
        }
        return list;
    }
}
